package com.wubotao.algorithm;

public class Insertion {
	
	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static void sort(Comparable[] data) {
		for (int index = 1; index < data.length; index++) {
			Comparable key = data[index];
			int position = index;
			// shift larger values to the right
			while (position > 0 && data[position - 1].compareTo(key) > 0) {
				data[position] = data[position - 1];
				position--;
			}
			data[position] = key;
		}
	}

	@SuppressWarnings("rawtypes")
	public static void main(String[] args) {
		Comparable[] c = { 4, 9, 23, 1, 45, 27, 5, 2 };
		sort(c);
		for (int i = 0; i < c.length; i++)
			System.out.println("插入排序：" + c[i]);
	}
}


